package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 230. 二叉搜索树中第K小的元素
 * @date 2025/3/13 22:18
 */
public class E230 {

    /**
     * 记录当前是第几小的元素
     */
    private int i = 0;

    /**
     * 记录结果
     */
    private int result = 0;

    /**
     * <h3>方法一：不完整的中序遍历</h3>
     * @param root 根节点
     * @param k 第k小的元素
     * @return 第k小的元素
     */
    public int kthSmallest(TreeNode root, int k) {
        dfs(root, k);
        return result;
    }

    /**
     * 中序遍历
     * @param root 根节点
     * @param k 第k小的元素
     */
    private void dfs(TreeNode root, int k) {
        // 当遍历到空节点时或者已经找到第k小的元素时，直接返回
        if(root == null || i == k) return;
        // 遍历左子树
        dfs(root.left, k);
        // 处理当前值，如果当前就是第k小的元素，则记录结果，并返回
        if(++i == k){
            result = root.val;
            return;
        }
        // 遍历右子树
        dfs(root.right, k);
    }
}
